package com.shm.algorithm;

import com.ruoyi.common.utils.clone.CloneUtil;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 首页商品数据分组
 *
 * @Author dam
 * @create 2023/8/30 14:12
 */
public class GroupDivide {
    /**
     * 最小间距
     */
    private double minOffSet = Double.MAX_VALUE;
    /**
     * 存储最好的第一组
     */
    public List<Long> bestGroup1 = null;

    public void search(List<Long> idList, Map<Long, Double> idAndRatioMap, Double sumAspectRatioOfColumn1, Double sumAspectRatioOfColumn2, Double messageAspectRatio) {
        List<Long> curGroup1 = new ArrayList<>();
        // 先搜索组1为空的方案
        double offSet = calculateGroup1DifHeifGroup2Hei(idList, curGroup1, idAndRatioMap, sumAspectRatioOfColumn1, sumAspectRatioOfColumn2, messageAspectRatio);
        if (Math.abs(offSet) < minOffSet) {
            // 找到更小的间距，保存最优解
            minOffSet = Math.abs(offSet);
            bestGroup1 = CloneUtil.arrayListClone(curGroup1);
        }
        // 递归搜索组1不为空的其他方案
        this.dfsSearch(idList, 0, curGroup1, idAndRatioMap, sumAspectRatioOfColumn1, sumAspectRatioOfColumn2,messageAspectRatio);
    }

    /**
     * 深度优先遍历搜索
     * @param idList
     * @param begin
     * @param curGroup1
     * @param idAndRatioMap
     * @param sumAspectRatioOfColumn1
     * @param sumAspectRatioOfColumn2
     * @param messageAspectRatio
     */
    public void dfsSearch(List<Long> idList, int begin, List<Long> curGroup1, Map<Long, Double> idAndRatioMap, Double sumAspectRatioOfColumn1, Double sumAspectRatioOfColumn2,Double messageAspectRatio) {
        if (begin == idList.size()) {
            // 递归完成
            return;
        }
        for (int i = begin; i < idList.size(); i++) {
            curGroup1.add(idList.get(i));
            // 计算组1的长度-组2的长度
            double offSet = calculateGroup1DifHeifGroup2Hei(idList, curGroup1, idAndRatioMap, sumAspectRatioOfColumn1, sumAspectRatioOfColumn2, messageAspectRatio);
            if (offSet > minOffSet) {
                // 如果当前差距已经大于最小差距，执行剪枝，因为如果再往第一组增加图片的话，那差距只会更大，没必要再往下搜索了
                // 删除最后一个元素
                curGroup1.remove(curGroup1.size() - 1);
                continue;
            } else if (Math.abs(offSet) < minOffSet) {
                // 找到更小的间距，保存最优解
                minOffSet = Math.abs(offSet);
                bestGroup1 = CloneUtil.arrayListClone(curGroup1);
            }
            dfsSearch(idList, i + 1, curGroup1, idAndRatioMap, sumAspectRatioOfColumn1, sumAspectRatioOfColumn2,messageAspectRatio);
            // 删除最后一个元素
            curGroup1.remove(curGroup1.size() - 1);
        }
    }

    /**
     * 计算第一组的图片的总高度 减去 第二组图片的总高度
     *
     * @param idList
     * @param group1
     * @param idAndRatioMap
     * @param sumAspectRatioOfColumn1
     * @param sumAspectRatioOfColumn2
     * @param messageAspectRatio
     * @return
     */
    private double calculateGroup1DifHeifGroup2Hei(List<Long> idList, List<Long> group1, Map<Long, Double> idAndRatioMap, Double sumAspectRatioOfColumn1, Double sumAspectRatioOfColumn2, Double messageAspectRatio) {
        // 设置初始值
        double sum1 = sumAspectRatioOfColumn1, sum2 = sumAspectRatioOfColumn2;
        for (Long id : idList) {
            if (group1.indexOf(id) == -1) {
                sum2 += idAndRatioMap.get(id);
                sum2 += messageAspectRatio;
            } else {
                sum1 += idAndRatioMap.get(id);
                sum1 += messageAspectRatio;
            }
        }
        return sum1 - sum2;
    }

}
